package practice_2025_8_18;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    // 存储数字 -> 字符 的映射关系
    Map<Character, String> hash;
    StringBuilder path;
    List<String> res;

    /**
     * 电话号码的字母组合
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        res = new ArrayList<>();
        path = new StringBuilder();
        // 处理特殊情况
        if (digits.length() == 0) {
            return res;
        }
        // 初始化
        hash = new HashMap<>();
        hash.put('1', "");
        hash.put('2', "abc");
        hash.put('3', "def");
        hash.put('4', "ghi");
        hash.put('5', "jkl");
        hash.put('6', "mno");
        hash.put('7', "pqrs");
        hash.put('8', "tuv");
        hash.put('9', "wxyz");
        dfs(digits, 0);
        return res;
    }

    public void dfs(String digits, int index) {
        // 递归出口
        if (index >= digits.length()) {
            res.add(path.toString());
            return;
        }
        // 继续递归
        String tmp = hash.get(digits.charAt(index));
        for(char ch: tmp.toCharArray()) {
            // 递归
            path.append(ch);
            dfs(digits, index + 1);
            // 回溯
            path.delete(path.length() - 1, path.length());
        }
    }
}